home *** CD-ROM | disk | FTP | other *** search
/ Gold Medal Software 2 / Gold Medal Software Volume 2 (Gold Medal) (1994).iso / archive / ntzip.arj / IM_LMAT.C < prev    next >
C/C++ Source or Header  |  1992-03-26  |  28KB  |  726 lines
  1. /*
  2.  
  3.  Copyright (C) 1990,1991 Mark Adler, Richard B. Wales, and Jean-loup Gailly.
  4.  Permission is granted to any individual or institution to use, copy, or
  5.  redistribute this software so long as all of the original files are included
  6.  unmodified, that it is not sold for profit, and that this copyright notice
  7.  is retained.
  8.  
  9. */
  10.  
  11. /*
  12.  *  im_lmat.c by Jean-loup Gailly.
  13.  *
  14.  *  PURPOSE
  15.  *
  16.  *      Identify new text as repetitions of old text within a fixed-
  17.  *      length sliding window trailing behind the new text.
  18.  *
  19.  *  DISCUSSION
  20.  *
  21.  *      The "implosion" process depends on being able to identify portions
  22.  *      of the input text which are identical to earlier input (within a
  23.  *      sliding window trailing behind the input currently being processed).
  24.  *
  25.  *      The most straightforward technique turns out to be the fastest for
  26.  *      most input files: try all possible matches and select the longest.
  27.  *      The key feature is of this algorithm is that insertion and deletions
  28.  *      from the string dictionary are very simple and thus fast. Insertions
  29.  *      and deletions are performed at each input character, whereas string
  30.  *      matches are performed only when the previous match ends. So it is
  31.  *      preferable to spend more time in matches to allow very fast string
  32.  *      insertions and deletions. The matching algorithm for small strings
  33.  *      is inspired from that of Rabin & Karp. A brute force approach is
  34.  *      used to find longer strings when a small match has been found.
  35.  *      A similar algorithm is used in freeze (by Leonid Broukhis) but the
  36.  *      algorithm used here is faster.
  37.  *         A previous version of this file used a more sophisticated algorithm
  38.  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
  39.  *      time, but has a larger average cost and uses more memory. However
  40.  *      the F&G algorithm may be faster for some highly redundant files if
  41.  *      the parameter max_chain_length (described below) is too large.
  42.  *
  43.  *  ACKNOWLEDGEMENTS
  44.  *
  45.  *      Rich Wales defined the interface, provided the necessary information
  46.  *      to ensure compatibility with pkunzip 1.0 (not an easy job) and
  47.  *      suggested the solution (n == 1 + n-1) adopted here.
  48.  *      The idea of lazy evaluation of matches is due to Jan Mark Wams, and
  49.  *      I found it in 'freeze' written by Leonid Broukhis.
  50.  *      Special thanks to Kai-Uwe Rommel for the OS/2 port, to Glenn J.
  51.  *      Andrews for the VMS port, and to many other info-zippers for testing.
  52.  *
  53.  *  REFERENCES
  54.  *
  55.  *      A description of the Rabin and Karp algorithm is given in the book
  56.  *          "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
  57.  *
  58.  *      Fiala,E.R., and Greene,D.H.
  59.  *          Data Compression with Finite Windows, CACM, 32,4 (1989) 490-595.
  60.  *
  61.  *  INTERFACE
  62.  *
  63.  *      ImpErr lm_init (int pack_level)
  64.  *          Initialize the "longest match" routines for a new file.
  65.  *          The global variable fd is an implicit parameter.
  66.  *
  67.  *      ImpErr lm_input (U_CHAR *block, U_INT count)
  68.  *          Process a block of input characters.
  69.  *
  70.  *      ImpErr lm_windup (void)
  71.  *          Flush out the remaining unprocessed input.
  72.  */
  73.  
  74. #include "implode.h"
  75.  
  76. /***********************************************************************
  77.  *
  78.  * Configuration parameters
  79.  */
  80.  
  81. #define MAX_MATCH_LENGTH  320
  82. /* The maximum match length. 320 = 64 + 256. (If the length is greater than
  83.  * 63, pkzip uses an extra byte.)
  84.  */
  85.  
  86. #define MAX_WBITS  13
  87. #define WSIZE (1 << MAX_WBITS)
  88. /* Maximum window size = 8K */
  89.  
  90. /* Constants used to dimension the hash table: */
  91. #define HASH_BITS  14
  92. /* HASH_BITS must be >= 13, see longest_match() */
  93.  
  94. #define HASH_SIZE (1<<HASH_BITS)
  95. #define HASH_MASK (HASH_SIZE-1)
  96.  
  97. #if defined(MSDOS) || defined(i386) || defined(mc68020) || defined(vax)
  98. #ifndef MIPS
  99. #   define UNALIGNED_OK
  100. #endif
  101.     /* Define this symbol if your target allows access to unaligned data.
  102.      * This is not mandatory, just a speed optimization. The compressed
  103.      * output is strictly identical.
  104.      */
  105. #endif
  106. #ifdef __TURBOC__
  107. #   define DYN_ALLOC
  108.     /* Turbo C 2.0 does not accept far static allocations in small model */
  109. #endif
  110.  
  111. /***********************************************************************
  112.  *
  113.  * Local data used by the "longest match" routines.
  114.  */
  115.  
  116. #if HASH_BITS <= 14
  117.    typedef unsigned short Hash;
  118. #else
  119.    /* Defined just for safety, since values > 14 do not speed up implosion */
  120.    typedef unsigned long Hash;
  121. #endif
  122.  
  123. typedef unsigned short Pos;
  124. typedef unsigned int  IPos;
  125. /* A Pos is an index in the character window. We use short instead of int to
  126.  * save space in the various tables. IPos is used only for parameter passing.
  127.  */
  128.  
  129. int near min_match_length;
  130. /* Minimum match length, 2 for binary files, 3 for ascii files.
  131.  * (bad luck for ebcdic users; not because they may not get optimal
  132.  * compression, but because they have to use ebcdic machines :-)
  133.  * A zero value means that the min_match_length is not yet determined.
  134.  */
  135.  
  136. U_CHAR near window[MAX_MATCH_LENGTH + WSIZE + BSZ];
  137. /* MAX_MATCH_LENGTH bytes are duplicated at both ends of the window,
  138.  * to speed up string comparisons. The BSZ extra bytes allow a block copy
  139.  * of the input buffer into the window instead of a copy one byte at a time.
  140.  */
  141.  
  142. #define MAX_DIST (WSIZE + BSZ)
  143. /* Maximum theoretical distance between two distinct bytes in the window.
  144.  * Actual distances are limited to bufsize.
  145.  */
  146.  
  147. #define NIL  MAX_DIST
  148. /* Tail of hash chains */
  149.  
  150. #ifdef DYN_ALLOC
  151.    Hash far *next = NULL;
  152.    Pos  far *prev = NULL;
  153. #else
  154.    Hash far next[MAX_DIST+1];
  155.    Pos  far prev[MAX_DIST+HASH_SIZE+1];
  156. #endif
  157. /* next is a link to a more recent string with same hash index, or to the head
  158.  * of a hash table chain if there is no such string. next[NIL] is used to
  159.  * avoid extra checks. next[s] is NIL if string s is not yet in the dictionary
  160.  *
  161.  * prev is a link to an older string with same hash index (first MAX_DIST
  162.  * values) or head of hash chain (last HASH_SIZE values). prev[NIL] is used
  163.  * to avoid extra checks.
  164.  */
  165. #define match_head (prev+(MAX_DIST+1))
  166.  
  167. Hash near ins_h;  /* hash index of string to be inserted. */
  168.  
  169. int near h_shift;
  170. /* Number of bits by which ins_h must be shifted at each
  171.  * input step. It must be such that after min_match_length steps, the oldest
  172.  * byte no longer takes part in the hash key, that is:
  173.  *   h_shift * min_match_length >= HASH_BITS
  174.  */
  175.  
  176. MATCH *ma_buf = NULL;
  177. /* Buffer used to speed up reading/writing to/from temp file */
  178. #define MA_BUFEND (ma_buf+MA_BUFSIZE)
  179.  
  180. MATCH *ma;
  181. /* Pointer to the most recent match. */
  182.  
  183. int near start_length;
  184. /* Matches not greater than this are discarded. This is used in the lazy match
  185.  * evaluation. If start_length > 1, ma is a valid guess of length start_length
  186.  * and ct_tally has not yet been called.
  187.  */
  188.  
  189.         int near strstart;      /* start of string to insert */
  190.         int near strsize;       /* length of string to insert */
  191.         int near match_length;  /* length of current best match */
  192.         int near bufsize;       /* # of slots in window */
  193.         int near checkpoint;    /* look for new match at this point */
  194. static  int      insert_point;  /* position of next input buffer */
  195.  
  196. static  int      max_lazy_match;
  197. /* We try lazy evaluation only for matches of length 2..max_lazy_match, to
  198.  * speed up the implosion. We use 0 for maximum speed, 0.9*MAX_MATCH_LENGTH
  199.  * for maximum compression.
  200.  */
  201.  
  202.         int near max_chain_length;
  203. /* To speed up implosion, hash chains are truncated to this length.
  204.  * A higher limit improves compression ratio but degrades the speed.
  205.  * We use 40 for maximum speed, 960 for maximum compression. Values
  206.  * below 20 are not recommended.
  207.  */
  208.  
  209. /* Values for max_lazy_match and max_chain_length, depending on the desired
  210.  * pack level (0..9). The values given below have been tuned to exclude
  211.  * worst case performance for pathological files. Better values may be
  212.  * found for specific files. Note that the current algorithm requires 
  213.  * max_lazy >= 2.
  214.  */
  215. typedef struct config {
  216.    int max_lazy;
  217.    int max_chain;
  218. } config;
  219.  
  220. static config configuration_table[10] = {
  221. /* 0 */ {2,                     MAX_MATCH_LENGTH/8}, /* maximum speed */
  222. /* 1 */ {4,                     MAX_MATCH_LENGTH/4},
  223. /* 2 */ {5,                     MAX_MATCH_LENGTH/2},
  224. /* 3 */ {MAX_MATCH_LENGTH/16,   MAX_MATCH_LENGTH/2},
  225. /* 4 */ {MAX_MATCH_LENGTH/16,   3*MAX_MATCH_LENGTH/4},
  226. /* 5 */ {MAX_MATCH_LENGTH/16,   MAX_MATCH_LENGTH},
  227. /* 6 */ {MAX_MATCH_LENGTH/16,   3*MAX_MATCH_LENGTH/2},
  228. /* 7 */ {MAX_MATCH_LENGTH/16,   2*MAX_MATCH_LENGTH},
  229. /* 8 */ {9*MAX_MATCH_LENGTH/10, 2*MAX_MATCH_LENGTH},
  230. /* 9 */ {9*MAX_MATCH_LENGTH/10, 3*MAX_MATCH_LENGTH}}; /* maximum compression */
  231.  
  232.  
  233. #define MIN(a,b) ((a) <= (b) ? (a) : (b))
  234. /* The arguments must not have side effects. */
  235.  
  236. #define EQUAL 0
  237. /* result of strncmp for equal strings */
  238.  
  239. /*  Prototypes for local functions */
  240.  
  241. static void   set_min_match_length OF ((U_CHAR *block, U_INT count));
  242.        ImpErr write_match OF ((IPos ma_start, int ma_length));
  243.        IPos   longest_match OF ((IPos cur_match));
  244.        ImpErr lm_process OF ((U_INT count));
  245.  
  246. /***********************************************************************
  247.  *
  248.  * Initialize the "longest match" routines for a new file.
  249.  * The global variable fd is an implicit parameter.
  250.  */
  251. ImpErr lm_init (pack_level)
  252.     int pack_level; /* 0: best speed, 9: best compression, other: default */
  253. {
  254.     register int i;
  255.  
  256.     /* Validate the arguments */
  257.     bufsize = fd.fd_bufsize;
  258.     strsize = MIN (fd.fd_strsize, MAX_MATCH_LENGTH);
  259.     if (bufsize > WSIZE)          return IM_BADARG;
  260.     if (bufsize < 2 * strsize)    return IM_BADARG;
  261.     if (pack_level < 0 || pack_level > 9) return IM_BADARG;
  262.  
  263.     /* Make sure "bufsize" is a power of 2 */
  264.     if ((bufsize & (bufsize - 1)) != 0) return IM_BADARG;
  265.  
  266.     /* Use dynamic allocation if compiler does not like big static arrays: */
  267. #ifdef DYN_ALLOC
  268.     if (prev == NULL) {
  269.        next = (Hash far*)farmalloc((U_INT)(MAX_DIST+9)*sizeof(Hash));
  270.        prev = (Pos far*) farmalloc((U_INT)(MAX_DIST+HASH_SIZE+9)*sizeof(Pos));
  271.        /* We allocate 16 extra bytes for the normalization under MSDOS */
  272.        if (prev == NULL || next == NULL) return IM_NOMEM;
  273.  
  274. #   if defined(MSDOS) && !defined(OS2)
  275.        /* Normalize to pointers with offset 0 (required by asm version).
  276.         * For OS/2, we can't of course play such nasty games.
  277.         */
  278. #define NORMALIZE(ptr) { \
  279.    *((int*)&ptr+1) += ((unsigned)(ptr-0) + 15) >> 4; \
  280.    *(int*)&ptr = 0; \
  281. }
  282.        NORMALIZE(prev); NORMALIZE(next);
  283. #   endif
  284.     }
  285. #endif /* DYN_ALLOC */
  286.     /* Initialize the hash tables. */
  287.     for (i = 0;  i < HASH_SIZE; i++) match_head[i] = NIL;
  288.     for (i = 0;  i <= MAX_DIST; i++) next[i] = NIL;
  289.     /* prev[0..MAX_DIST] will be initialized on the fly */
  290.     ins_h = 0;
  291.  
  292.     /* Assume strsize zeros before the input (bytes beyond strsize
  293.      * can be garbage):
  294.      */
  295.     memset((char*)window, 0, MAX_MATCH_LENGTH);
  296.     /* It is not necessary to duplicate this at the end of the window.
  297.      * Duplication will start only after the first wrap around.
  298.      */
  299.     insert_point = MAX_MATCH_LENGTH;
  300.  
  301.     /* Force a check for the file type (ascii/binary) and set the default
  302.      * configuration parameters:
  303.      */
  304.     min_match_length = 0;
  305.     max_lazy_match   = configuration_table[pack_level].max_lazy;
  306.     max_chain_length = configuration_table[pack_level].max_chain;
  307.  
  308.     /* Do not report matches before the first strsize strings have been
  309.      * inserted in the suffix tree:
  310.      */
  311.     strstart = 0;
  312.     checkpoint = strsize;
  313.     if (ma_buf == NULL) {
  314.         ma_buf = (MATCH *) malloc ((unsigned) (MA_BUFSIZE * sizeof (MATCH)));
  315.         if (ma_buf == NULL) return IM_NOMEM;
  316.     }
  317.     ma = ma_buf - 1;
  318.     start_length = 1;
  319.  
  320.     /* All done. */
  321.     return IM_OK;
  322. }
  323.  
  324. /***********************************************************************
  325.  *
  326.  * Output the match info.
  327.  * IN assertions: The matching strings start at strstart and ma_start
  328.  *    and have a length of ma_length bytes.
  329.  *    If ma_length is not greater than start_length, ma_start is garbage.
  330.  *    strstat == checkpoint. If start_length > 1, ma is the
  331.  *    previous match which has not yet been output.
  332.  * OUT assertion: checkpoint is reset according to the match length
  333.  *    actually chosen.
  334.  *    ma is set to the current match, with start_length set appropriately.
  335.  */
  336. ImpErr write_match(ma_start, ma_length)
  337.     IPos ma_start;           /* start of matched string */
  338.     int ma_length;           /* length of complete match */
  339. {
  340.     int ma_dist = 0;         /* distance of current match */
  341.  
  342.     /* ma_length can be too large towards the end of the input: */
  343.     if (ma_length > strsize) ma_length = strsize;
  344.  
  345. #ifdef DEBUG
  346.     /* check that the match is indeed a match */
  347.     if (ma_length > start_length &&
  348.         strncmp(window + ma_start, window + strstart, ma_length) != EQUAL) {
  349.         fprintf(stderr,
  350.             "write_match: ma_start %d, strstart %d, ma_length %d\n",
  351.             ma_start, strstart, ma_length);
  352.         exit(1);
  353.     }
  354. #endif
  355.     /* PKUNZIP accepts most overlapping matches.  However, when the
  356.      * distance has the value 1, versions of PKUNZIP prior to 1.10 don't
  357.      * handle the overlap properly -- and version 1.10 handles the
  358.      * overlap correctly only if the length is limited to 62 plus the
  359.      * minimum match length; i.e., only if there is no supplementary
  360.      * length byte.  (From phone conversation with Phil Katz, 23 January
  361.      * 1991.) The compression ratio is generally better when we do not
  362.      * limit the match length to 64, so we remove distance-one matches
  363.      * completely. (But PKUNZIP 1.01 also rejects some distance-two matches.
  364.      * This could be fixed but would degrade compression.)
  365.      */
  366.     if (ma_length > 1) {
  367.         ma_dist = strstart - ma_start;
  368.         if (ma_dist < 0) ma_dist += MAX_DIST;
  369.         if (ma_dist == 1) {
  370.             /* keep the previous match if it was delayed */
  371.             if (start_length > 1) {
  372.                 ma_length = 1;
  373.             } else {
  374.                 /* Truncate the match to 1 */
  375.                 ImpErr retcode = write_match(ma_start, 1);
  376.                 if (retcode != IM_OK) return retcode;
  377.  
  378.                 /* Emit a match with a distance of two and a length reduced by
  379.                  * one. This reduced match may be delayed.
  380.                  */
  381.                 checkpoint = ++strstart;
  382.                 retcode = write_match(ma_start, ma_length-1);
  383.                 strstart--;
  384.                 return retcode; /* Leave checkpoint unchanged */
  385.             } /* start_length > 1 */
  386.         } /* ma_dist == 1 */
  387.     } /* ma_length > 1 */
  388.  
  389.     /* If the previous match has been delayed, keep it or prefer the
  390.      * current match:
  391.      */
  392.     if (start_length > 1) {
  393.         /* Keep the previous match if it is not shorter than the current one.
  394.          * Otherwise, emit only the first byte of the previous match,
  395.          * followed by the current match. If we have a delayed match for
  396.          * the last bytes of the input file, the next match will necessarily
  397.          * be smaller, so ct_tally will correctly be called for the delayed
  398.          * match.
  399.          */
  400.         if (start_length >= ma_length) {
  401.             /* Keep the previous match */
  402.             if (start_length == 2) {
  403.                 ma->ma_dist = - ma->ma_dist;
  404.                 ma->l.ma_litc[1] = window[strstart]; /* litc[0] already set */
  405.             } else {
  406.                 ma->l.ma_length = start_length; /* overwrite ma->l.ma_litc */
  407.             }
  408.             checkpoint = strstart + start_length - 1;
  409.             start_length = 1;
  410.             return ct_tally (ma);
  411.         }
  412.         /* Shorten the previous match to zero */
  413.         ma->ma_dist = 0; /* keep ma->l.ma_litc */
  414.         start_length = 1;
  415.         (void) ct_tally (ma); /* ignore result, ct_tally cannot fail */
  416.     }
  417.  
  418.     if (++ma == MA_BUFEND) {
  419.         ma = ma_buf;
  420.         if (twrite ((char *) ma, sizeof(MATCH), MA_BUFSIZE, fd.fd_temp)
  421.             != MA_BUFSIZE) return IM_IOERR;
  422.     }
  423.  
  424.     /* Keep the current match as guess only if its length is small,
  425.      * trying to find a better match at the next step. If speed is not
  426.      * critical, we use this lazy mechanism for all lengths.
  427.      */
  428.     if (ma_length > 1) {
  429.         ma->ma_dist = ma_dist;
  430.         if (ma_length <= max_lazy_match) {
  431.            /* Set ma_litc[0]: this is the only way to identify the unmatched
  432.             * data if the delayed match will be truncated to 1. It is also
  433.             * useful if ma_length == 2: it may be more efficient in this case
  434.             * to encode the individual characters rather than the match info.
  435.             */
  436.             ma->l.ma_litc[0] = window[strstart];
  437.             start_length = ma_length;
  438.             checkpoint = strstart + 1;
  439.             return IM_OK;
  440.         }
  441.         /* At this point, ma_length >= 3, no need for ma_litc */
  442.         ma->l.ma_length = ma_length;
  443.         checkpoint = strstart + ma_length;
  444.     } else {
  445.         ma->ma_dist = 0;
  446.         ma->l.ma_litc[0] = window[strstart]; /* ma_litc[1] is not required */
  447.         checkpoint = strstart + 1;
  448.     }
  449.     return ct_tally (ma);
  450.     /* Keep start_length == 1 */
  451. }
  452.  
  453. /***********************************************************************
  454.  *
  455.  * Determine the minimum match length, based on the type of data
  456.  * in the given input buffer: 2 for binary data, 3 otherwise. Set also
  457.  * h_shift according to the chosen min_match_length, and reduce
  458.  * max_chain_length for binary files.
  459.  *    If the guess about data type is wrong, this only affects the
  460.  * compression ratio and speed but not the correctness of the algorithms.
  461.  * If there are more than 20% bytes which seem non ascii in the first
  462.  * 500 bytes, we assume that the data is binary. (We accept data
  463.  * with a few high bits set as ascii to take into account special
  464.  * word processor formats.)
  465.  */
  466. static void set_min_match_length (block, count)
  467.     U_CHAR *block;          /* input data */
  468.     U_INT  count;           /* # of input char's */
  469. {
  470.     int non_ascii = 0;
  471.     min_match_length = 3;  /* Default ascii */
  472.     if (count >= 500) {
  473.         count = 500;
  474.         while (--count != 0) {
  475.             if (*block <= 6 || *block >= 0x80) non_ascii++;
  476.             block++;
  477.         }
  478.         if (non_ascii > 100) {
  479.             min_match_length = 2;
  480.             max_chain_length >>= 2;
  481.         }
  482.     }
  483.     h_shift = (HASH_BITS+min_match_length-1)/min_match_length;
  484. #ifdef DEBUG
  485.     fprintf(stderr," (min_match_length %d) ", min_match_length);
  486. #endif
  487. }
  488.  
  489. /***********************************************************************
  490.  *
  491.  * Insert string s in the dictionary and set last_match to the previous head
  492.  * of the hash chain (the most recent string with same hash key).
  493.  * IN  assertion: all calls to to INSERT_STRING are made with consecutive
  494.  *    input characters, so that a running hash key can be computed from the
  495.  *    previous key instead of complete recalculation each time.
  496.  */
  497. #define INSERT_STRING(s, last_match) \
  498. { \
  499.     ins_h = ((ins_h<<h_shift) ^ window[s + min_match_length-1]) & HASH_MASK; \
  500.     prev[s] = last_match = match_head[ins_h]; \
  501.     next[last_match] = prev[next[s] = ins_h + MAX_DIST+1] = s; \
  502. }
  503.     /* next[NIL] is garbage, we can overwrite it if s is a tail */
  504.  
  505. /***********************************************************************
  506.  *
  507.  * Remove string s from the dictionary, or do nothing if s is not yet
  508.  * in the dictionary.
  509.  * IN assertion: s is the tail of its hash chain (the oldest string).
  510.  */
  511. #define DELETE_STRING(s)  {prev[next[s]] = NIL;}
  512. /* No effect if next[s] == NIL (s not in dictionary) */
  513.  
  514. /***********************************************************************
  515.  *
  516.  * Find the longest match starting at the given string. Return its position
  517.  * and set its length in match_length. Matches shorter or equal to
  518.  * start_length are discarded, in which case match_length is unchanged
  519.  * and the result position is NIL.
  520.  * IN assertions: cur_match is the head of the hash chain for the current
  521.  *   string (strstart) and is not NIL, and start_length >= 1
  522.  */
  523. #if !defined(MSDOS) || defined(NO_ASM)
  524. /* For MSDOS, a version of this routine written in assembler is in im_lm.asm.
  525.  * The algorithms are strictly equivalent, so the C version can be used
  526.  * instead if you do not have masm or tasm. (Update the makefile in this case.)
  527.  */
  528. IPos longest_match(cur_match)
  529.     IPos cur_match;
  530. {
  531.     register U_CHAR *match;                   /* pointer in matched string */
  532.     register U_CHAR *scan = window + strstart;/* pointer in current string */
  533.     register int len;                         /* length of current match */
  534.     IPos cur_best = NIL;                      /* best match so far */
  535.     register int ma_length = start_length;    /* best match length so far */
  536.     int chain_count = max_chain_length;       /* used to limit hash chains */
  537.     typedef unsigned short US;
  538.     typedef unsigned long  UL;
  539. #ifdef UNALIGNED_OK
  540.     register US scan_start = *(US*)scan;
  541.     register US scan_end   = *(US*)(scan+ma_length-1);
  542. #else
  543.     register U_CHAR scan_start = *scan;
  544.     register U_CHAR scan_end1  = scan[ma_length-1];
  545.     register U_CHAR scan_end   = scan[ma_length];
  546. #endif
  547.     do {
  548.         match = window + cur_match;
  549.         /* Skip to next match if the match length cannot increase
  550.          * or if the match length is less than 2:
  551.          */
  552. #ifdef UNALIGNED_OK
  553.         /* This code assumes sizeof(unsigned short) == 2 and
  554.          * sizeof(unsigned long) == 4. Do not use UNALIGNED_OK if your
  555.          * compiler uses different sizes.
  556.          */
  557.         if (*(US*)(match+ma_length-1) != scan_end ||
  558.             *(US*)match != scan_start) continue;
  559.  
  560.         len = min_match_length - 4;
  561.         /* If min_match_length == 3, it is not necessary to compare
  562.          * scan[2] and match[2] since they are always equal when the other
  563.          * bytes match, given that the hash keys are equal and that
  564.          * HASH_BITS >= 8.
  565.          */
  566. #       define ML MAX_MATCH_LENGTH
  567.         do {} while ((len+=4) < ML && *(UL*)(scan+len) == *(UL*)(match+len));
  568.  
  569.         if (*(US*)(scan+len) == *(US*)(match+len)) len += 2;
  570.         if (scan[len] == match[len]) len++;
  571.  
  572. #else /* UNALIGNED_OK */
  573.         if (match[ma_length] != scan_end ||
  574.             match[ma_length-1] != scan_end1 || *match != scan_start)
  575.            continue;
  576.         /* It is not necessary to compare scan[1] and match[1] since they
  577.          * are always equal when the other bytes match, given that
  578.          * the hash keys are equal and that h_shift+8 <= HASH_BITS,
  579.          * that is, when the last byte is entirely included in the hash key.
  580.          * The condition is equivalent to
  581.          *       (HASH_BITS+2)/3 + 8 <= HASH_BITS
  582.          * or: HASH_BITS >= 13 (see set_min_match_length()).
  583.          * Also, we check for a match at ma_length-1 to get rid quickly of
  584.          * the match with the suffix of the match made at the previous step,
  585.          * which is known to fail.
  586.          */
  587.         len = 1;
  588.         do {} while (++len < MAX_MATCH_LENGTH && scan[len] == match[len]);
  589.  
  590. #endif /* UNALIGNED_OK */
  591.  
  592.         if (len > ma_length) {
  593.             cur_best = cur_match, ma_length = len;
  594.             if (len >= strsize) break;
  595. #ifdef UNALIGNED_OK
  596.             scan_end = *(US*)(scan+ma_length-1);
  597. #else
  598.             scan_end1  = scan[ma_length-1];
  599.             scan_end   = scan[ma_length];
  600. #endif
  601.         }
  602.     } while (--chain_count != 0 && (cur_match = prev[cur_match]) != NIL);
  603.  
  604.     if (ma_length > start_length) match_length = ma_length;
  605.     return cur_best;
  606. }
  607. #endif /* MSDOS */
  608.  
  609. /***********************************************************************
  610.  *
  611.  * Process a block of input characters, generating zero or more match
  612.  * info records as appropriate.
  613.  * IN assertion: count <= BSZ
  614.  */
  615. ImpErr lm_input (block, count)
  616.     U_CHAR *block;          /* input data */
  617.     U_INT  count;           /* # of input char's */
  618. {
  619.     if (count == 0) return IM_OK;
  620.  
  621.     /* Determine the input file type if this is the first call */
  622.     if (min_match_length == 0) set_min_match_length (block, count);
  623.  
  624.     if (insert_point + count <= sizeof(window)) {
  625.         memcpy((char*)window + insert_point, (char*)block, count);
  626.  
  627.     } else {
  628.         int remain = sizeof(window)-insert_point;
  629.         memcpy((char*)window + insert_point, (char*)block, remain);
  630.  
  631.         memcpy((char*)window + MAX_MATCH_LENGTH,
  632.                (char*)block + remain, count - remain);
  633.     }
  634.     insert_point += count;
  635.     if (insert_point > MAX_DIST) {
  636.         /* Duplicate the end of the window */
  637.         memcpy((char*)window,
  638.                (char*)window + MAX_DIST,
  639.                MIN (insert_point - MAX_DIST, MAX_MATCH_LENGTH));
  640.     }
  641.     if (insert_point >= sizeof(window)) insert_point -= MAX_DIST;
  642.     return lm_process(count);
  643. }
  644.  
  645. /***********************************************************************
  646.  *
  647.  * Process a block of characters already inserted in the window
  648.  * IN assertion: count > 0
  649.  */
  650. #if !defined(MSDOS) || defined(NO_ASM)
  651. ImpErr lm_process (count)
  652.     U_INT  count;           /* number of bytes to process */
  653. {
  654.     ImpErr retcode;         /* as usual */
  655.     IPos cur_match;         /* starting point for longest match search */
  656.     IPos best_match = NIL;  /* longest match found */
  657.     int delete_point;       /* position of next string to remove */
  658.  
  659.  
  660.     delete_point = strstart - bufsize + MAX_MATCH_LENGTH - 1;
  661.     if (delete_point < 0) delete_point += MAX_DIST;
  662.  
  663.     /* Process the input block. */
  664.     do {
  665.         /* Insert the string window[strstart .. strstart+strsize-1] in the
  666.          * dictionary, and set cur_match to the head of the hash chain:
  667.          */
  668.         INSERT_STRING(strstart, cur_match);
  669.  
  670.         if (strstart == checkpoint) {
  671.             /* Find the longest match, discarding those <= start_length */
  672.             match_length = 0;
  673.             if (cur_match != NIL) {
  674.                 best_match = longest_match (cur_match);
  675.                 /* longest_match updates match_length if longer match found */
  676.             }
  677.             retcode = write_match (best_match, match_length);
  678.             if (retcode != IM_OK) return retcode;
  679.         }
  680.         /* Remove the oldest string from the dictionary, except if we have not
  681.          * yet created bufsize dictionary entries. We could avoid this
  682.          * deletion and check instead for obsolete pointers in
  683.          * longest_match(), but this would be slower.
  684.          */
  685. #if (MAX_DIST & (MAX_DIST-1)) != 0
  686.         if (++delete_point == MAX_DIST) delete_point = 0;
  687. #else
  688.         delete_point = (delete_point + 1) & (MAX_DIST-1);
  689. #endif
  690.         DELETE_STRING (delete_point);
  691.  
  692.         if (++strstart == MAX_DIST) {
  693.             strstart = 0, checkpoint -= MAX_DIST;
  694.         }
  695.     } while (--count != 0);
  696.     return IM_OK;
  697. }
  698. #endif /* MSDOS */
  699.  
  700. /***********************************************************************
  701.  *
  702.  * Wind up processing by flushing unprocessed input. For normal processing,
  703.  * this routine is called twice (by imp_size then imp_clear) and the
  704.  * second call does nothing. In case of error, this routine is called only
  705.  * by imp_clear().
  706.  */
  707. ImpErr lm_windup()
  708. {
  709.     ImpErr retcode;
  710.     int matches;
  711.  
  712.     /* Process the remaining input. */
  713.     while (strsize > 0) {
  714.        retcode = lm_process (1);
  715.        if (retcode != IM_OK) return retcode;
  716.        --strsize;
  717.     }
  718.     /* Flush the match buffer. */
  719.     if ((matches = ma-ma_buf+1) != 0 && matches != 
  720.         twrite ((char *) ma_buf, sizeof(MATCH), matches, fd.fd_temp)) {
  721.         return IM_IOERR;
  722.     }
  723.     ma = ma_buf - 1;
  724.     return IM_OK;
  725. }
  726.